package com.example.recursion;

/**
 * @Date 2022/7/10
 * @Created by Jonathan
 */
public class CoinChange {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5, 10};
        int aim = 100;
        final int result = getResult(coins, aim);
        final int result2 = process2(coins, aim);
        System.out.println(result);
        System.out.println(result2);
    }


    private static int getResult(int[] coins, int aim) {
        return process(coins, 0, aim);
    }

    private static int process(int[] coins, int index, int rest) {
        if (index == coins.length) { // base case
            return rest == 0 ? 1 : 0;
        }

        int ans = 0;
        for (int zhang = 0; coins[index] * zhang <= rest; zhang++) {
            ans += process(coins, index + 1, rest - coins[index] * zhang);
        }
        return ans;
    }


    /**
     * 改写成dp的方式
     *
     * @return
     */
    private static int process2(int[] coins, int aim) {
        int n = coins.length;
        int[][] dp = new int[n + 1][aim + 1];
        // base case
        dp[n][0] = 1;
        // dp[0..n-1] = 0 这个是默认值
        for (int index = n - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int zhang = 0; coins[index] * zhang <= rest; zhang++) {
                    ways += dp[index + 1][rest - coins[index] * zhang];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];

    }
}
